一、學習目標

• 掌握雙指針（Two Pointers）技巧的兩大變形：
  • 對撞型雙指針（Two-end）
  • 滑動視窗型雙指針（Sliding Window）
• 能夠解決與「區間長度」、「數值範圍」、「總和大小」相關的子陣列問題。
• 熟悉在排序陣列中搜尋符合條件的組合（例如：和為某值的兩數、三數）。

二、觀念說明

雙指針技巧解析

雙指針技術是競賽與面試中極常出現的技巧，適用於處理：

• 兩個序列的配對問題（ex. CSES Apartments）
• 單一序列中尋找滿足條件的區間（ex. 子陣列總和、最短/最長長度）
• 固定一端，變動另一端 的結構（如固定左端，右端向右滑）

1. 對撞型 Two Pointers（Two-End）

• 適用於已排序陣列。
• 左右各一個指標，向中間靠攏。
• 常用於「兩數和問題」、「三數和問題」。

範例邏輯：

int left = 0, right = nums.size() - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return true;
    else if (sum < target) left++;
    else right--;
}

2. 滑動視窗型 Two Pointers（Sliding Window）

• 適用於正整數或可累加的序列。
• 左右指標控制一個區間 [l, r]，右指標負責擴展，左指標負責收縮。
• 常見於「找最短區間」、「固定和」、「子陣列個數」等問題。

三、CSES實戰演練

題目1 : Apartments

原題:
https://cses.fi/problemset/task/1084

題意:
有 n 位申請人與 m 間公寓，每位申請人希望租的房間大小為 xi，每間公寓實際大小為 yj，只要誤差在 k 以內（|xi-yj|≤k）即可配對。

解題思路:

• 將兩邊陣列（申請人與房間）皆排序。
• 使用兩個指標 i, j 分別掃描申請人與房間。
• 若房間太小 → j++
• 若房間太大 → i++
• 若符合誤差條件 → 計數 + i++, j++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> applicants(n), apartments(m);
    for (int &x : applicants) cin >> x;
    for (int &y : apartments) cin >> y;

    sort(applicants.begin(), applicants.end());
    sort(apartments.begin(), apartments.end());

    int i = 0, j = 0, count = 0;
    while (i < n && j < m) {
        if (abs(applicants[i] - apartments[j]) <= k) {
            count++;
            i++, j++;
        } else if (apartments[j] < applicants[i] - k) {
            j++;
        } else {
            i++;
        }
    }
    cout << count << "\n";
    return 0;
}

題目2 : Sum of Two Values

原題:
https://cses.fi/problemset/task/1640
題意：
給定長度為 n 的陣列與目標值 x，找出陣列中是否有兩個不同的數 a+b=x，並輸出其原始位置（1-indexed）。

解題思路：

• Step 1：儲存原始位置（pair<int, int>）
• Step 2：排序陣列（根據值）
• Step 3：使用 left, right 指針搜尋總和 = x
  • 若和太小，左指針右移
  • 若和太大，右指針左移
  • 若剛好等於 x，輸出對應 index

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, x;
    cin >> n >> x;
    vector<pair<int,int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i+1; // 儲存原始 index
    }
    sort(a.begin(), a.end());

    int l = 0, r = n-1;
    while (l<r) {
        int sum = a[l].first + a[r].first;
        if (sum == x) {
            cout << a[l].second << " " << a[r].second << "\n";
            return;
        } else if (sum < x) l++;
        else r--;
    }
    cout << "IMPOSSIBLE\n";
    return 0;
}

四、Leetcode實戰演練

題目1 : 3Sum

原題:
https://leetcode.com/problems/3sum/description/

題意:
給定整數陣列 nums，找出所有不重複的三元組 a + b + c = 0。

解題思路:

• 先排序陣列 → O(n log n)
• 固定第一個數 i，用雙指針在 i+1 ~ end 中找剩下兩數
• 若總和小於 0，右移 left；若總和大於 0，左移 right

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left = i+1, right = nums.size()-1;
            while (left<right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum==0) {
                    res.push_back({nums[i], nums[left], nums[right]});
                    while (left<right && nums[left] == nums[left+1]) left++;
                    while (left<right && nums[right] == nums[right-1]) right--;
                    left++; right--;
                } 
                else if (sum<0) left++;
                else right--;
            }
        }
        return res;
    }
};

題目2 : Minimum Size Subarray Sum

原題:
https://leetcode.com/problems/minimum-size-subarray-sum/description/

題意:
給定正整數陣列與目標值 target，求連續子陣列總和 ≥ target 的 最短長度，若無解回傳 0。

解題思路:滑動窗口

• left 與 right 控制一個區間
• 總和未達標 → 擴大窗口（右移 right）
• 總和達標 → 嘗試縮小窗口（右移 left）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, sum = 0, res = INT_MAX;
        for (int right=0; right < nums.size(); right++) {
            sum += nums[right];
            while (sum >= target) {
                res = min(res, right-left+1);
                sum-=nums[left++];
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};